翻訳と辞書 Words near each other ・ Schreiber Diesels ・ Schreiber Foods ・ Schreiber theory ・ Schreiber's fringe-fingered lizard ・ Schreiber, Ontario ・ Schreibersite ・ Schreibkraft ・ Schreier ・ Schreier conjecture ・ Schreier coset graph ・ Schreier domain ・ Schreier refinement theorem ・ Schreier vector ・ Schreier's lemma ・ Schreierstoren ・ Schreier–Sims algorithm ・ Schreinemaker's analysis ・ Schreiner ・ Schreiner Airways ・ Schreiner University ・ Schreiner's ・ Schreiteria ・ Schreiteriana pectinicornis ・ Schrekk & Grauss ・ Schrempf (surname) ・ Schrems ・ Schrems bei Frohnleiten ・ Schrenck Siberian salamander ・ Schrenk ・ Schretstaken Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Schreier–Sims algorithm ： ウィキペディア英語版 Schreier–Sims algorithm The Schreier–Sims algorithm is an algorithm in computational group theory named after mathematicians Otto Schreier and Charles Sims. Once performed, it allows a linear time computation of the order of a finite group, group membership test (is a given permutation contained in a group?), and many other tasks. The algorithm was introduced by Sims in 1970, based on Schreier's subgroup lemma. The timing was subsequently improved by Donald Knuth in 1991. Later, an even faster randomized version of the algorithm was developed. == Background and timing == The algorithm is an efficient method of computing a base and strong generating set (BSGS) of a permutation group. In particular, an SGS determines the order of a group and makes it easy to test membership in the group. Since the SGS is critical for many algorithms in computational group theory, computer algebra systems typically rely on the Schreier–Sims algorithm for efficient calculations in groups. The running time of Schreier–Sims varies on the implementation. Let $G\; \backslash leq\; S\_n$ be given by $t$ generators. For the deterministic version of the algorithm, possible running times are: * $O(n^2\; \backslash log^3\; |G|\; +\; tn\; \backslash log\; |G|)$ requiring memory $O(n^2\; \backslash log\; |G|\; +\; tn)$ * $O(n^3\; \backslash log^3\; |G|\; +\; tn^2\; \backslash log\; |G|)$ requiring memory $O(n\; \backslash log^2\; |G|\; +\; tn)$ The use of Schreier vectors can have a significant influence on the performance of implementations of the Schreier–Sims algorithm. For Monte Carlo variations of the Schreier–Sims algorithm, we have the following estimated complexity: : $O(n\; \backslash log\; n\; \backslash log^4\; |G|\; +\; tn\; \backslash log\; |G|)$ requiring memory $O(n\; \backslash log\; |G|\; +\; tn)$ In modern computer algebra systems, such as GAP and Magma, an optimized Monte Carlo algorithm is typically used. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Schreier–Sims algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.